package style.Leetcode.初级算法.array.array_20220729_3_旋转数组;

/**
 * 给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
 *
 * 示例 1:
 * 输入: nums = [1,2,3,4,5,6,7], k = 3
 * 输出: [5,6,7,1,2,3,4]
 * 解释:
 * 向右轮转 1 步: [7,1,2,3,4,5,6]
 * 向右轮转 2 步: [6,7,1,2,3,4,5]
 * 向右轮转 3 步: [5,6,7,1,2,3,4]
 *
 * 示例 2:
 * 输入：nums = [-1,-100,3,99], k = 2
 * 输出：[3,99,-1,-100]
 * 解释: 
 * 向右轮转 1 步: [99,-1,-100,3]
 * 向右轮转 2 步: [3,99,-1,-100]
 *
 *
 */
public class Solution {

    /**
     *  思路：
     *      1、借助一个同等大小的临时数组
     *      2、原数组（index+k）% length 等于 临时数组index
     */
    public void rotate1(int[] nums, int k) {
        int length = nums.length;
        int[] tempArr = new int[length];

        for (int index = 0; index < length; index++) {
            tempArr[index] = nums[index];
        }

        for (int index = 0; index < length; index++) {
            nums[(index+k)%length] = tempArr[index];
        }

//        for (int i = 0; i < nums.length; i++) {
//            System.out.println(nums[i]);
//        }
    }

    /**
     *  思路：
     *     1、全部反转
     *     2、反转前 k 个
     *     3、反转剩下的
     */
    public void rotate2(int[] nums, int k) {
        reserve(nums, 0, nums.length-1);
        reserve(nums, 0, k-1);
        reserve(nums, k, nums.length-1);

        for (int index = 0; index < nums.length; index++) {
            System.out.println(nums[index]);
        }
    }

    /**
     * 反转数组
     * @param nums
     * @param start
     * @param end
     */
    public void reserve(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
//        solution.rotate1(new int[]{1,2,3,4,5,6,7}, 3);
        solution.rotate2(new int[]{1,2,3,4,5,6,7}, 3);
    }
}
